package NC;

// 01背包
public class NC145 {
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[] dp = new int[V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= vw[i-1][0]; j--) {
                dp[j] = Math.max(dp[j-vw[i-1][0]]+vw[i-1][1],dp[j]);
            }
        }
        return dp[V];
    }
}
